/*
 * @lc app=leetcode.cn id=338 lang=cpp
 *
 * [338] 比特位计数
 */

// @lc code=start
class Solution {
public:
    /**
     * @brief 0:0000 1:0001 2:0010  3:0011
     *               3:0011 4:0100  6:0110
     *               5:0101 8:1000 12:1100
     *                              (偶数，就等于他)
     * 
     * 由上可见：
        1、如果 i 为偶数，那么f(i) = f(i/2) ,因为 i/2 本质上是i的二进制左移一位，低位补零，所以1的数量不变。
        2、如果 i 为奇数，那么f(i) = f(i - 1) + 1， 因为如果i为奇数，那么 i - 1必定为偶数，而偶数的二进制最低位一定是0，
        那么该偶数 +1 后最低位变为1且不会进位，所以奇数比它上一个偶数bit上多一个1，即 f(i) = f(i - 1) + 1
     * @param num 
     * @return vector<int> 
     */
    vector<int> countBits(int num) {
        vector<int> res(num + 1 , 0);
        for(int i = 0 ;i <= num ; i++)
        {
            if(i%2 == 0)
            {
                //偶数
                res[i] = res[i / 2];
            }
            else
            {
                res[i] = res[i / 2] + 1;
            }
        }
        return res;
    }
};
// @lc code=end

